Detection of round (i.e., circular and/or elliptical) objects in a digital image is a common task in many image-processing applications. For example, it is used in industrial applications, such as automatic inspections and assembly, in which many components are round-shaped. Traffic signs in European, Asian, and other countries have circular shapes, and automatic detection of these signs often involves circle/ellipse detection as a first step. Circle-detection techniques are also employed in, for example, localizing inner and outer boundaries of a human iris for iris-recognition algorithms used in biometric identification applications.
One method of detecting round objects in an image uses chain codes. A chain code is an image-compression format for efficiently representing foreground objects in a monochrome image by storing information representing only the contour (also known as the border or the boundary) of the objects. An x,y coordinate corresponding to an arbitrary point on the contour of a foreground object is first located. The object's contour is traversed from this x,y coordinate and, for each new pixel discovered in the contour, a symbol representing the direction of travel from the previous pixel is identified. For example, if the last pixel in the traversed contour was to the left of the next pixel, the symbol “E” might be stored (i.e., the contour just moved “east” one pixel); if the last pixel was below the next pixel, the symbol “N” might be stored (i.e., the contour just moved “north” one pixel). The object is thus represented by a start point and a series of directional movements relative to that start point that (eventually) lead back to the start. FIG. 1A illustrates a directional compass 100 defining a type of eight-direction chain code called a Freeman chain code, and FIG. 1B illustrates a circle 102 labeled with Freeman chain-code directions. The circle 102 might be represented, therefore, by the initial (x,y) point 104 and the Freeman chain codes 0, 1, 2, 3, 4, 5, 6, 7. More-complicated objects have, of course, more complicated chain codes.
Once a chain code is computed for a shape, it may be analyzed to attempt to determine certain properties of the shape (e.g., its type). For example, a histogram of the chain code (i.e., the number of 0s, 1s, 2s, etc. appearing in the chain code) may be analyzed. If the distribution of codes in the histogram is approximately uniform, for example, the shape may be a circle because, by definition, a circle transitions through every chain code, and does so for an equal amount of time per code. If the distribution is “symmetric” (i.e., if the number of opposite chain-code pairs 0/4, 1/5, 2/6, and 3/7 are roughly equal), the object may be a circle or ellipse. The “aspect ratio” of the histogram (i.e., the ratio of the horizontal-edge codes 0/4 to the vertical-edge codes 2/6) may be one for a circle and greater than one, but less than a maximum ellipticity/“ovalness” value, for an ellipse. The aspect ratio may be alternatively computed as the average of the ratios 0/4 to 2/6 and 1/5 to 3/7 to account for possible rotation away from horizontal or vertical of any ellipses in the image.
This method of shape identification (and specifically, the identification of circles and ellipses), while simple and efficient, has several drawbacks. The contour must be traversed in its entirety so that the complete histogram may be computed, thus wasting computation time by analyzing (what will eventually be identified as) non-round objects. Furthermore, the method may lead to many false-positive results, because certain non-round shapes (e.g., squares and rectangles) have chain-code histograms that are symmetric and/or have aspect ratios equal to one. Still other shapes, such as the shape 200 shown in FIG. 2, may have uniform histograms of chain-code symbols (i.e., the symbol 200 includes six codes of type “0,” six codes of type “1,” etc.) and yet be non-circular. Finally, this method is susceptible to occlusion or noise in the image; if, for example, an object of interest is occluded by another object or noise in the image prevents its full contour from being traced, the histogram produces misleading data (if it can even be computed at all).
Other methods of detecting round objects in images may be more accurate but consume greater computing resources, require more computing time, or both. A Hough-transform-based approach (using, specifically, a circular Hough transform) requires a three-dimensional accumulator array and a complicated “voting” technique to determine most-probable centers and radii of round objects, a process that requires a large amount of memory and computational power. A Markov-chain-based approach to building chain codes is unreliable at least because the probability of a particular chain code occurring is heavily dependent upon past chain codes (i.e., a side of a rectangle is assigned many “0” codes, for example, and the likelihood of a “3,” “4,” or “5” code is nearly zero), and this dependency reduces the accuracy of the Markov chain. Still other methods add position information (e.g., x,y coordinates) to each chain code, but this extra information greatly expands the size of the input data, rendering a main benefit of the chain codes moot. A need therefore exists for a way to quickly, efficiently, and accurately detect round objects in images.